package array.practice;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MergeArray<T extends Comparable<T>> {
    public static void main(String[] args) {
        MergeArray<Integer> mergeArray = new MergeArray<>();
        Integer[] input = {4, 5, 3, 6, 7, 9};
        Integer[] input2 = {1, 1, 3, 6, 7, 9, 1};
//        System.out.println(Arrays.toString(mergeArray.mergeOnList(input, input2)));
//        System.out.println(Arrays.toString(mergeArray.merge(input, input2)));
        System.out.println(Arrays.toString(mergeArray.compareAndMerge(input, input2)));


    }

    /**
     * 利用List
     *
     * @param arr
     * @param brr
     * @return
     */
    public T[] mergeOnList(T[] arr, T[] brr) {

        List<T> aList = new ArrayList<>(Arrays.asList(arr));
        List<T> bList = new ArrayList<>(Arrays.asList(brr));

        aList.addAll(bList);
        T[] res = (T[]) aList.toArray();
        Arrays.sort(res);
        return res;
    }

    /**
     * 合并后排序
     *
     * @param arr
     * @param brr
     * @return
     */
    public T[] merge(T[] arr, T[] brr) {

        T[] res = (T[]) new Object[arr.length + brr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        for (int j = 0, k = arr.length; j < brr.length; j++, k++) {
            res[k] = brr[j];
        }

        Arrays.sort(res);
        return res;
    }

    /**
     * 边比较边合并
     * @param arr
     * @param brr
     * @return
     */
    public T[] compareAndMerge(T[] arr, T[] brr) {

        T[] res = (T[]) new Integer[arr.length + brr.length];
        int top = 0;
        int bottom = 0;
        for (int i = 0; i < res.length; i++) {
            if (top<arr.length && smaller(arr[top], brr[bottom])) {
                res[i]=arr[top];
                top++;
            }else {
                res[i]=brr[bottom];
                bottom++;
            }
        }


        return res;
    }


    public boolean smaller(T t1, T t2) {
        return t1.compareTo(t2) <= 0;
    }
}
